#include <iostream>
using namespace std;

struct Node {
  int val;
  Node *next;
  Node(int nval) : val(nval), next(nullptr) {}
};

void pt(Node *p) {
  while (p) {
    cout << p->val << " ";
    p = p->next;
  }
  cout << endl;
}

void FindHalf2(Node *Head, Node **Half) {
  if (Head == nullptr) {
    *Half = nullptr;
    return;
  }
  Node *quick = Head;
  Node *slow = Head;
  while ((quick->next != nullptr) && (quick->next->next != nullptr)) {
    slow = slow->next;
    quick = quick->next->next;
  }
  *Half = slow;
}

void FindHalf(Node *Head, Node **Half) {
  int temp = 2;
  Node *quick = Head;
  Node *slow = Head;
  while (quick != nullptr) {
    if (temp == 0) {
      slow = slow->next;
      temp = 2;
    } else {
      quick = quick->next;
      --temp;
    }
  }
  *Half = slow;
}

Node *ReverseLinkList(Node *Head) {
  if (Head == nullptr) {
    return nullptr;
  }
  Node *reversefirst = Head->next;
  Node *reversesecond = Head;
  while (reversefirst != nullptr) {
    Node *p = reversefirst->next;
    reversefirst->next = reversesecond;
    reversesecond = reversefirst;
    reversefirst = p;
  }
  Head->next = nullptr;
  return reversesecond;
}

bool Huiwen(Node *Head) {
  Node *half = nullptr;
  FindHalf(Head, &half);
  Node *NewHead = ReverseLinkList(half);
  pt(NewHead);
  while (Head != nullptr && NewHead != nullptr) {
    if (Head->val != NewHead->val) {
      return false;
    }
    NewHead = NewHead->next;
    Head = Head->next;
  }
  return true;
}

int main(int argc, char *argv[]) {
  Node a(1);
  Node b(2);
  Node c(1);
  a.next = &b;
  b.next = &c;
  c.next = nullptr;
  pt(&a);
  cout << Huiwen(&a) << endl;
  return 0;
}
